//https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum/?envType=daily-question&envId=2023-10-24


class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        if(target < n) return 0;
        int mod = 1e9 + 7;
        long long ans = 0;
        //第一维为使用骰子个数，第二维为骰子点数之和，存储得到对应结果的方案数量
        vector<vector<long>> dp(n + 1, vector<long>(target + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = i; j <= target; j++)
            {
                for(int num = 1; num <= k && num <= j; num++)
                {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - num]) % mod;
                }
            }
        }
        return dp[n][target];
    }
};